package sort

//有向无环图
type dag struct {
	vertex int           //顶点
	edge   map[int][]int //有向边
}

//创建图
func NewDag(v int) *dag {
	dag := new(dag)
	dag.vertex = v
	dag.edge = map[int][]int{}
	i := 0
	for i < v {
		dag.edge[i] = make([]int, 0)
		i++
	}
	return dag
}

//添加边
func (dag *dag) AddEdge(t int, s int) {
	dag.edge[t] = push(dag.edge[t], s)
}

//取出切片第一个
func pop(edge []int) (int, []int) {
	if len(edge) > 0 {
		a := edge[0]
		b := edge[1:]
		return a, b
	} else {
		return -1, edge
	}
}

//推入切片
func push(edge []int, value int) []int {
	return append(edge, value)
}

//添加边
func (dag *dag) KhanSort() []int {
	var inDegree = make(map[int]int)
	var queue []int
	for i := 1; i <= dag.vertex; i++ {
		for _, m := range dag.edge[i] {
			inDegree[m]++
		}
	}
	for i := 1; i <= dag.vertex; i++ {
		if inDegree[i] == 0 {
			queue = push(queue, i)
		}
	}
	var data []int
	for len(queue) > 0 {
		var now int
		now, queue = pop(queue)
		data = push(data, now)
		for _, k := range dag.edge[now] {
			inDegree[k]--
			if inDegree[k] == 0 {
				queue = push(queue, k)
			}
		}
	}
	return data
}

func (dag *dag) DfsSort() []int {
	inverseList := make(map[int][]int)
	//初始化逆向邻接表
	for i := 1; i <= dag.vertex; i++ {
		for _, k := range dag.edge[i] {
			inverseList[k] = append(inverseList[k], i)
		}
	}
	visited := make([]bool, dag.vertex+1)
	visited[0] = true
	data := make([]int, 0)
	for i := 1; i <= dag.vertex; i++ {
		if visited[i] == false {
			visited[i] = true
			dfs(i, inverseList, visited, &data)
		}
	}
	return data
}

func dfs(vertex int, inverseList map[int][]int, visited []bool, data *[]int) {
	for _, w := range inverseList[vertex] {
		if visited[w] == true {
			continue
		} else {
			visited[w] = true
			dfs(w, inverseList, visited, data)
		}
	}
	*data = push(*data, vertex)
}
